package com.niuke;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @ClassName : NC175
 * @Author : kele
 * @Date: 2023/4/2 15:40
 * @Description :
 */
public class NC175 {

    public boolean isValidString(String s) {

        LinkedList<Integer> arr_char = new LinkedList<>();
        LinkedList<Integer> arr_star = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (c == '(') {
                arr_char.push(i);
            } else if (c == '*') {
                arr_star.push(i);
            } else {

                if (!arr_char.isEmpty()) {
                    arr_char.pop();
                } else if (!arr_star.isEmpty()) {
                    arr_star.pop();
                } else {
                    return false;
                }
            }
        }

        while (!arr_char.isEmpty()) {

            if (arr_star.isEmpty()) {
                return false;
            } else {
                if (arr_char.pop() > arr_star.pop()) {
                    return false;
                }
            }

        }

        return true;
    }

}
